A timetable-generating system for scheduling classes in primary schools

Ng Sin-chun, Andrew K F Lui and Cheng Wing-yee
Open University of Hong Kong
Hong Kong SAR, China

Each semester, schools and academic institutions face the rather tedious and problematic task of scheduling classes, students, teachers and classrooms in a fixed number of time-slots, subject to various constraints. In fact, timetabling difficulties are considered as NP-complete problems as there is no known efficient way of finding the best solution. An effective timetable should consider the best utilization of human and space resources, which makes it an optimization problem. This paper focuses mainly on solving difficulties in scheduling classes in primary schools.

In order to solve the scheduling problem, an automated timetable-generating system for primary schools has been developed. The system can facilitate data entry and generate timetables with different views automatically, and it can be used in preparing the timetables for a whole school. However, the users must define each teacher’s teaching assignments and input all the constraints before generating the timetables. With all the required data, the system can generate a complete timetable that fulfils all the requirements based on different scheduling algorithms. The system involves two parts -- the main system and the back-end database server -- which can be run on any Microsoft Windows computers. For communication between the system and database server, a JDBC-ODBC bridge has been used.

This paper investigates different optimization methods such as the Greedy algorithm, Tabu search and Genetic algorithm (GA) for resolving timetabling difficulties. Also presented is a modified algorithm which consists essentially of two parts: random search and local search. The algorithm first generates an initial solution through random search and then improves the result by local search. The modified algorithm has been developed to reduce the running time and complexity of GA, which is considered to be inefficient in generating optimal solutions for timetables.

The simulation results show that the Tabu search can produce better timetables in an efficient way. Tabu involves less search time than the Greedy algorithm and GA, but GA and the modified algorithm can produce several different near optimal solutions for different runs.

The paper discusses the background to the problem of class scheduling, outlines the system design and database connection and evaluates different optimization methods for timetabling.